// tspcluster - Traveling Salesman Problem
// Copyright (C) 2006  Frederik Carlier
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

using System;
using System.Collections.Generic;

namespace UGent.Tsp
{
    /// <summary>
    /// Generates the permutations of n elements.
    /// 
    /// This implementation is based on <i>A. Nijenhuis and H. Wilf, Combinatorial Algorithms 
    /// for Computer and Calculators (2nd Ed., Academic Press), Chapter 7: Next Permutation 
    /// of n Letters</i>. 
    /// 
    /// </summary>

    public class PermutationIterator : IEnumerator<int[]>
    {
        bool isFirst = true;
        bool even;
        bool hasNext;
        int[] a;
        int s, d, l, m, tmp;


        /// <summary>
        /// Constructor.
        /// </summary>
        /// <param name="n">number of elements to be permuted.</param>
        public PermutationIterator(int n)
        {
            if (n < 1)
            {
                throw new ArgumentOutOfRangeException("n < 1");
            }
            this.a = new int[n];
            this.hasNext = true;
        }

        public bool HasNext
        {
            get
            {
                return this.hasNext;
            }
        }

        /// <summary>
        /// Returns the next permutation of n elements. Each permutation is 
        /// represented by an integer array of size n.
        /// </summary>
        /// <returns>an array of size n containing a permutation.</returns>
        /// <exception cref="InvalidOperationException">there are no more permutations.</exception>
        public int[] next()
        {
            if (!hasNext)
            {
                throw new InvalidOperationException("no next");
            }

            if (isFirst)
            {
                isFirst = false;
                even = true;

                for (int i = 0; i < a.Length; i++)
                {
                    a[i] = i;
                }

                if (a.Length < 2)
                {
                    this.hasNext = false;
                }
            }
            else
            {
                if (even)
                {
                    even = false;
                    tmp = a[0]; a[0] = a[1]; a[1] = tmp;  // swap a[0] and a[1]

                    if (a.Length < 3)
                    {
                        this.hasNext = false;
                        return (int[])a.Clone();
                    }

                    // Determine if this is the last permutation.
                    // If a.length is even the last permutation is {1 2 3 4 ..... (a.length-1) 0}
                    //	If a.length is odd the last permutation is  {2 3 4 ..... (a.length-1) 1 0}
                    int r = a.Length % 2;
                    int f = 1 + r;
                    if (a[a.Length - 1] == 0 && a[0] == f)
                    {
                        if ((r == 0 && a[a.Length - 2] == a.Length - 1) ||
                            (r != 0 && a[a.Length - 2] == 1 && a[a.Length - 3] == a.Length - 1))
                        {
                            this.hasNext = false;
                            for (int k = 0; k < a.Length - 1 - f; k++)
                            {
                                if (a[k + 1] != a[k] + 1)
                                {
                                    this.hasNext = true;
                                    break;
                                }
                            }
                        }
                    }
                }
                else
                {
                    even = true;
                    s = 0;
                    int i;
                    for (i = 1; i < a.Length; i++)
                    {
                        d = 0;
                        for (int j = 0; j < i; j++)
                        {
                            if (a[j] > a[i]) d++;
                        }
                        s += d;

                        l = 0;
                        if (d != i * (s % 2)) // (s is odd and d_i < i) or (s is even and d_i > 0)
                        {
                            m = ((s + 1) % 2) * a.Length;
                            for (int j = 0; j < i; j++)
                            {
                                // if (sign(a[j] - a[i]) == sign(a[j] - m))
                                if ((a[j] - a[i]) * (a[j] - m) > 0)
                                {
                                    continue;
                                }
                                m = a[j];
                                l = j;
                            }
                            tmp = a[i]; a[i] = a[l]; a[l] = tmp;  // swap a[i] and a[l]
                            break;
                        }
                    }
                }
            }
            return (int[])a.Clone();
        }

        int[] current;
        bool disposed;

        #region IEnumerator<int[]> Members

        public int[] Current
        {
            get
            {
                if (disposed)
                    throw new ObjectDisposedException("PermutationIterator");

                return current;
            }
        }

        #endregion

        #region IDisposable Members

        public void Dispose()
        {
            disposed = true;
        }

        #endregion

        #region IEnumerator Members

        object System.Collections.IEnumerator.Current
        {
            get
            {
                if (disposed)
                    throw new ObjectDisposedException("PermutationIterator");

                return (object)current;
            }
        }

        public bool MoveNext()
        {
            if (disposed)
                throw new ObjectDisposedException("PermutationIterator");

            if (!hasNext)
                return false;

            current = next();
            return true;
        }

        public void Reset()
        {
            isFirst = true;
        }

        #endregion
    }
}
